1. Field of the Invention
The present invention generally relates to a coding apparatus and method, recording medium and a program, and more particularly to a coding apparatus and method, recording medium and a program, suitable for use in converting an m-bit information word continuously into an n-bit code word with DC control bits for DC control of a code sequence being inserted in a sequence of information.
This application claims the priority of the Japanese Patent Application No. 2003-079556 filed on Mar. 24, 2003, the entirety of which is incorporated by reference herein.
2. Description of the Related Art
Many of various types of recorder/players and communications devices are designed for a reduced rate of errors, caused by coding of input information, of digitally transmitted information.
Referring now to FIG. 1, there is schematically illustrated in the form of a block diagram a digital signal processing circuit included in a typical conventional recorder/player indicated with a reference 1.
As shown, the digital signal processing circuit of the recorder/player 1 includes an encoder 11. The encoder 11 encodes an information sequence continuously supplied into a ratio of m:n (m is data bit length before coding, and n is a data bit length after coding) to generate a sequence of binary recording codes. It should be noted here that “m”, “n” and “m-n” will be referred to as “information word length”, “code word length” and “code rate” or “coding rate”, respectively.
The digital signal processing circuit includes also a recording/playback unit 12. The recording/playback unit 12 is composed of a magnetic head, optical pickup, control circuit to control the driving of the magnetic head and optical pickup, etc. to records a recording code supplied from the encoder 11 to a recording medium (not shown). Also, the recording/playback unit 12 reads a signal from the recording medium, and outputs a reproduced analog wave to an analog equalizer 13 also included in the digital signal processing circuit. The analog equalizer 13 equalizes the reproduced wave from the recording/playback unit 12 to a predetermined target equalization characteristic.
The digital signal processing circuit includes also an A-D converter 14. The A-D converter 14 converts the supplied equalized signal into a digital read signal. As shown, the A-D converter 14 includes a PLL (phase-locked loop). This PLL may be a hybrid digital PLL that makes only a phase error detection in a digital section thereof or a full-digital PLL that makes both a phase error detection and a signal synchronization in a digital section thereof.
Also, in case the equalization by the analog equalizer 13 is not sufficient, a digital equalizer may be provided between the A-D converter 14 and a code detector 15 also included in the digital signal processing circuit. It should be noted that in this case, a lowpass filter may be provided in place of the analog equalizer 13.
The above code detector 15 is supplied with a digital read signal (equalize signal) and converts it into a code (namely, it detects a code). Recently, it has become a common way to use a soft-decision detector such as a Viterbi detector or the like for the code detector 15. A decoder 16 also included in the digital signal processing circuit is supplied with a detection code continuously supplied, decodes it into a detection in formation in a ratio of n: m, and outputs the detection information as a sequence of detection information.
As shown in FIG. 1, various codes are used in practice in the coding effected in the encoder 11. Many different types of recorder/players adopt, for example, a (d, k) RLL (run-length limited) code in which d is a minimal number of 0's between 1's in a code sequence (minimum run) and k is a maximum number of 0's between 1's (maximum run) as in the NRZI (nonreturn-to-zero-inverted recording) modulation in which a recorded rectangular wave is inverted on one bit.
Especially in many optical players using an optical pickup for reading signals, a minimum run-length limited code with a minimum run d of more than one “0” is used to reduce the deterioration in quality of a read signal, due to the nonlinearity of the optical pickup. The compact disk (CD) recorder/players and music-playing mini disk (MD) recorder/players, having been popular, employ a (2, 10) RLL code of 8/17 in coding ratio called “EFM (eight to fourteen modulation)”, and the MD DAT2 used in the data-recording mini disk recorder/players adopt a (1, 7) RLL code of 2/3 in coding rate, for example.
Also, the (d, k) RLL code is not adopted only in the recorder/players. A (1, 13) RLL code of 2/3 in coding rate is employed in the radio communications device using an infrared ray called “IrDA-VFIr (infrared data association, very fast infrared), for example.
Of the (d, k) RLL codes, the EFM code is a fixed-length code and the (1, 7) RLL code is a variable-length code. Generally, the variable-length code is encoded based on either a look-ahead code conversion table or a finite-state code conversion table.
FIGS. 2 and 3 show the well-known look-ahead code conversion tables of the (1, 7) RLL codes (by Cohn-Jacoby-Bates). FIG. 2 shows a basic code conversion table, and FIG. 3 shows an irregular code conversion table. An information sequence is encoded according to the basic code conversion table in FIG. 2. When an information sequence as listed in the irregular code conversion table in FIG. 3 is supplied, the irregular code conversion table in FIG. 3 is preferentially applied to encode the information sequence (see the U.S. Pat. No. 4,337,458 to M. Cohn, G. Jacoby and C. Bates, for example).
On the assumption that one block is a minimum unit of coding (equivalent to 2 bits of input information or 3 bits of code in the basic code conversion table in FIG. 2, for example), the encoder 11 that encodes information according to the code conversion tables in FIGS. 2 and 3 has to look ahead an information sequence for one block in order to encode information. Also, the look-ahead code conversion tables in FIGS. 2 and 3 can be converted into finite-state code conversion tables, respectively, by re-assigning, to an information word, a code word having been made to lag behind the information word by the same amount as a necessary look-ahead amount for the encoder 11.
Note here that the above “re-assignment of a code word made to lag behind an information word by one block” is to assign a code work 001 to an information word 00 while a preceding information word is 10 since two code words 001 and 000 are assigned to two information words 10 and 00, respectively, as in FIG. 3.
FIG. 4 shows a finite state-type 5-state code conversion table for (1, 7) RLL codes converted according to the look-ahead code conversion tables in FIGS. 2 and 3. In FIG. 4, three bits shown before a slash (/) indicate a code word and a figure shown after the slash indicates a transition.
That is, the finite-state code conversion table in FIG. 4 is derived from assignment of a 3-bit code word made to lag one block to an information word each of 2 bits in the look-ahead code conversion tables in FIGS. 2 and 3 (see the article “The Power Spectrum of Run-Length-Limited Codes” by A. Gallopoulos, C. Heegard and P. Siegel, IEEE Trans. on Com., Vol. 37, No. 9, pp. 906–917, September 1989, for example).
In case the encoder 11 has encoded information according to the look-ahead code conversion tables in FIGS. 2 and 3, it can output only a code word delayed one block in relation to a code word assigned to an input information word by one block for looking ahead the information word. Also, in case the encoder 11 has encoded information according to the finite-state code conversion table 4, it is necessary to look ahead any information word. However, the finite-state code conversion table in FIG. 4 is different from the code conversion tables in FIGS. 2 and 3 in that a code word delayed one block is assigned to an information word.
That is, a code sequence resulted from encoding an information sequence according to the look-ahead code conversion tables in FIGS. 2 and 3 will be identical to a code sequence resulted from encoding according to the finite-state code conversion table in FIG. 4. Therefore, the look-ahead code conversion table and finite-state code conversion table appear to present different codes, respectively, but they are different only in notation of a coding rule from each other. However, on the assumption that the internal circuit of the encoder 11 is constructed in faithful accordance with the coding rule of the code conversion tables, the encoder 11 will be different in circuit construction from each other depending upon which the code conversion table adopted is, a look-ahead or finite state-type one.
Also, in case the code is not of a variable length but of a fixed length, the code conversion table is of the finite state type alone since an information sequence has not to be looked ahead. It can be discriminated depending upon which the same code word is assigned to, a plurality of information words or a single information word, whether a code represented according to the finite-state code conversion table is a variable-length one or a fixed-length one.
Also, although the look-ahead code conversion table has to be designed by a heuristic approach, the finite-state code conversion table can theoretically be designed with the use of a method called “ACH (Adler-Coppersmith-Hassner) algorithm”.
The ACH algorithm used for designing a finite-state code conversion table will be explained herebelow. In the ACH algorithm, a number of bits of a target code word is first taken as a parameter and a vector called “approximate characteristic vector” having dimensions corresponding to a number of states is determined based on a finite state transition diagram of the code. Next, there is prepared a finite states table including the same number of finite states in the finite state transition diagram as that of elements in the approximate characteristic vector, and then each of operations called “state splitting” and “state merging” is repeated to finally provide a simplified finite states table.
In the ACH algorithm, multiple approximate characteristic vectors exist and the last finite states table determined varies depending upon the first approximate characteristic vector determined. Since there are many options in each of the state splitting and state merging operations, however, using the same approximate characteristic vector will not always result in the same last finite states table.
By appropriately assigning each code in a finite states table thus obtained to necessary information word, it is possible to provide a finite-state code conversion table. Also, all codes designed by this method have a finite code word constraint length and can be decoded independently of any state. That is, it is well known that a code designed by the method is sliding-block decodable.
The ACH algorithm is referred in detail to the article “Algorithm for Sliding Block Codes” by R. Adler, D. Coppersmith and M. Hassner, IEEE Trans. on Information Theory, Vol. IT-29, No. 1, pp. 5–22, January 1983, for example.
FIG. 5 shows an 8-state finite state transition diagram premised on the NRZI modulation and which provides a (1, 7) RLL code. It should be noted here that a state number in the finite state transition diagram shown in FIG. 5 does not corresponding to a state number in the finite-state code conversion table.
Generally, two approximate characteristic vectors [2, 3, 3, 3, 2, 2, 2, 1] and [3, 5, 5, 4, 4, 4, 3, 2] are known as 8-dimensional ones determined according to the finite state transition diagram in FIG. 5. The value of each element in the approximate characteristic vector indicates a number by which each state in the finite state transition diagram (a so-called number of stet stripping) is first divided. For example, the 5-state code conversion table in FIG. 4 can be determined according to the look-ahead code conversion tables in FIGS. 2 and 3 and also theoretically as an approximate characteristic vector [3, 5, 5, 4, 4, 4, 3, 2] using an ACH algorithm determined according to the finite state transition diagram in FIG. 5. On the other hand, by determining a finite-state code conversion table using the ACH algorithm as the approximate characteristic vector [2, 3, 3, 3, 2, 2, 2, 1], there can be provided a 4-state finite-state code conversion table.
FIG. 6 shows a finite-state 4-state code conversion table of a (1, 7) RLL code by Weathers-Wolf. The code conversion table in FIG. 6 is known as a minimum-state finite-state code conversion table of the (1, 7) RLL code (see the article “A New Rate 2/3 Sliding Block Code for the (1, 7) Runlength Constraint with the Minimal Number of Encoder States” by A. D. Weathers and J. K. Wolf, IEEE Trans. on Info. Theory, Vol. 37, No. 3, pp. 908–913, May 1991, for example).
Generally in an optical disk recorder/player or an optical disk player, low-frequency component of a code spectrum has to be suppressed to some extent to extract a servo signal used in a low-frequency band. Since a low-frequency component of a read signal in a data area is superposed as a noise on the extracted servo signal if the low-frequency component of the code spectrum is not suppressed at all, the servo signal will have the quality thereof deteriorated considerably.
The low-frequency component of a code spectrum can effectively be suppressed by controlling the DC component of a code sequence so that a running digital sum (RDS) of the code sequence will have a digital-sum variation (DSV) as small as possible. The “RDS” referred to herein is a sum of code polarities represented by ±1 in a modulated recording code sequence or transmission code sequence, namely, in a code sequence after NRZI-modulated in case the code sequence is based on the NRZI modulation.
Conventionally, the DC control of a code sequence is done using primarily the following three methods:
The first one of the methods is to encode data irrespectively of the DSV of a code sequence to be checked the RDS of the code sequence, and then insert DC control bits at constant intervals into the code sequence so that the DSV of the code sequence is as small as possible. On the assumption that the DC control bit is an RLL control bit as the case may be, however, the insertion of DC control bits may be followed by a first coding so that the RLL limitation on the code sequence can be kept.
The codes to which the above first method is applicable include the previously mentioned EFM code actually used in CD and MD, for example. In the case of EFM code, however, if a certain information sequence is given continuously, any DC control cannot be done to keep the limitation on a (2, 10) RLL code and DSV of the code will not be finite in some cases. However, since commonly used input information has a high randomness, the above will not be any practical problem.
The above first method is advantageous in that it is applicable to an arbitrary RLL code. However, a large number of DC control bits has to be inserted into a code sequence in order to keep the RLL limitation and thus the code redundancy including the influence of the DC control bits is apt to be increased.
The second one of the above three methods is to pre-design a code conversion table of a finite state type so that the DSV of a code sequence will be as small as possible. The codes to which the second method is applicable include a (2, 10) RLL code called “EFMPlus” used to convert an 8-bit information word into a 16-bit code word. This EFMPlus code is actually used as a recording code for DVD (digital versatile disk). The aforementioned EFM code is of a fixed length. On the other hand, the EFMPlus code has a variable length in which a plurality of information words is assigned the same code word.
However, an EFMPlus code includes 256 Information words, of which only 95 are DC-controllable. If any ones of the other 161 information words are successively included in the EFMPlus code, the DSV will not be finite. Also in this case, however, input information used has a high randomness as a rule as in the above-mentioned EFM code. Thus the above will not be any problem.
The second one of the aforementioned methods is advantageous in which it is not necessary to insert any DC control bit. For some codes, it is difficult to design a code conversion table with a high coding rate. In many cases, the code conversion table is so complex that the encoder and decoder are complex in construction.
The third method is to pre-assign a code word to an information word so that two's complement of a sum of information words coincides with that of a sum of code words and insert DC control bits at constant intervals into an information sequence so that the DSV of a code sequence is as small as possible. After a code word is assigned by the third method, the inversion of a code following a DC control bit to be inserted is assured whether the DC control bit is 0 or 1. Thus, a code sequence can be DC-controlled efficiently.
The code word assignment by the third method is called “PP (parity preserving) word assignment” because it is done in such a manner that the parity of an information sequence always coincides with that of a code sequence.
More specifically, the PP word assignment worked by Kahlman and Immink in 1994 is such that in the look-ahead code conversion table, code words are assigned to information words in order to meet the following expression (1) (see the U.S. Pat. No. 5,477,222 to J. Kahlman and A, Immink, for example):p=q  (1)where p is a complement of a sum of information words and q is a complement of a sum of code words.
In the third method, any DC control bits inserted in an information sequence will not disturb the RLL limitation on a code sequence. Thus, when suppressing low-frequency components of a code spectrum with an equal effect, adoption of the third method will often permit to reduce the redundancy of the DC control bits as compared with the first method in which DC control bits are inserted in a code sequence.
In the third method, however, the inversion of a code sequence is assured through selection of DC control bits but the inversion of the RDS within a control interval is not always assured. Therefore, if information pieces whose RDS polarity will not be inverted are supplied successively whether either 0 or 1 is selected as a DC control bit, the DSV will not be finite as the case may be. However, since commonly used input information has a high randomness similarly to the aforementioned EFM and EFMPlus codes, the above will not be any practical problem.
Also, in case the DC control method of inserting DC control bits into an information sequence is used, the RDS polarity of a code sequence can be inverted with a certain probability even if the PP code word assignment is not doe in a look-ahead code conversion table used, the DC control of the code sequence is not quite impossible. That is, the PP code word assignment can advantageously be used because a code sequence can be subjected to an efficient DC control by considerably increasing the probability in inversion of the RDS of the code sequence at the time DC control bits are inserted into an information sequence.
For a practical PP assignment of codes in the code conversion table, only the look-ahead code conversion table is known. Namely, for the finite-state code conversion table determined from the ACH algorithm, there is known no PP code word assignment method, which was definitely stated by K. Immink, one of the Inventors of the PP code word assignment (see “Codes for Mass Data Storage” by K. Immink, Shannon Foundation Publishers, Netherlands, p. 290, 1999).
Also, the code represented according to the first look-head code conversion table for the PP code word assignment, disclosed in the above U.S. Pat. No. 5,477,222, was a (1, 8) RLL code. Currently, it is known that a look-ahead code conversion table for the PP code word assignment can be designed for the (1, 7) RLL code as well.
FIGS. 7 and 8 show look-ahead code conversion tables for the PP code word assignment of the (1, 7) RLL code.
FIG. 7 shows a basic data conversion table for use to encode an information sequence in normal times, and FIG. 8 shows an irregular code conversion table for use to encode an information sequence at a fault. When an information sequence is encoded according to the basic code conversion table in FIG. 7, it results in a (1, 8) RLL code. Coding the (1, 8) RLL code according to the irregular code conversion table in FIG. 8 results in a (1, 7) RLL code. In other words, in case an information sequence as in the irregular code conversion table is supplied for coding, the irregular code conversion table in FIG. 8 is used for the (1, 7) RLL code preferentially over the basic code conversion table in FIG. 7. In any of the basic code conversion table in FIG. 7 and irregular code conversion table in FIG. 8, the two's complement of a sum of information words completely coincides with that of a sum of code words (see the Japanese Published Unexamined Patent Application No. 1999-346154, for example).
As described in the above Japanese Published Unexamined Patent Application No. 1999-346154, a long sequence of minimum runs adversely affects the bit error rate when a defocusing, tangential tilt or the like has occurred in the optical disk recorder/player or optical disk player. On this account, it has been proposed to limit the maximum number of minimum runs in sequence to six (6) by adding the irregular code conversion table to the look-ahead code conversion tables in FIGS. 7 and 8. It should be noted here that in a code sequence “001(01)r00”, r≦R where (01)r is a representation of (01) repeated r times in succession and R is a maximum number of minimum runs are repeated R times in succession on the assumption that the minimum run is “1” and the modulation method is the NRZI modulation, for example.
FIG. 9 shows a look-ahead irregular code conversion table to which the PP code word assignment is applied. This look-ahead irregular code conversion table is added to the basic code conversion table and irregular code conversion table in FIGS. 7 and 8 to limit the maximum number of minimum runs in sequence of a (1, 7) RLL code to six (6).
Also in the irregular code conversion table in FIG. 9, the two's complement of a sum of information words coincides with that of a sum of code words. By encoding information under the coding rule adopted in the code conversion tables in FIGS. 7 and 8 and also that in the irregular code conversion table in FIG. 9, it is possible to limit the maximum number of minimum runs in sequence to six (6) with the PP code word assignment being maintained.
The (1, 7) RLL code represented according to the look-ahead code conversion tables shown in FIGS. 7, 8 and 9 and to which the PP code word assignment is applied is adopted in the recording code for the Blu-ray which is the next-generation optical disk recorder/player.
As above, the PP (parity preserving) code word assignment is one of the excellent techniques for efficient DC control of a code sequence. More precisely, the PP code word assignment has to be done according to look-ahead code conversion tables and designed by a heuristic approach. For this reason, there have been known very few code conversion tables actually using the PP code word assignment.
On the other hand, the finite-state code conversion table can theoretically be designed using the ACH algorithm. Therefore, if a code word assignment method effective similarly to the PP code word assignment used in the look-ahead code conversion table can be found, it is possible to theoretically design a code conversion table superb in DC control efficiency.
Also, techniques for conversion of a look-ahead code conversion table into a finite-state code conversion table have been disclosed for conversion of variable-length codes, but there has been disclosed no technique for conversion of a finite-state code conversion table into a look-ahead code conversion table. Namely, no concrete ways of such conversions are yet known. If a finite-state code conversion table can be converted into a look-ahead code conversion table, it will be possible to easily make clear the differences between the code word assignment in the aforementioned finite-state code conversion table and the conventional PP code word assignment.
For encoding information under the coding rule in a look-ahead code conversion table in which the PP code word assignment having been disclosed heretofore is used, the construction of the aforementioned encoder 11 will be more complicated than in case the conventional coding method is used in the look-ahead code conversion table.
For example, in the look-ahead code conversion tables in FIGS. 7 and 8, the necessary looked-ahead amount of an information sequence is 3 blocks. So, when a code word delayed 3 blocks is converted into a finite-state code conversion table via re-assignment to an information word, it will have 104 states. In the encoder 11, the coding rule of the finite-state code conversion table should not always be checked. However, since the large number of states as a result of the conversion to the finite-state code conversion table means the coding rule of the look-ahead code conversion table is complex, the construction of the encoder 11 will be complicated as a rule.
Especially when the maximum number of minimum runs in sequence is limited finitely, the encoder 11 will be constructed to be very complicated. For example, in case the look-ahead code conversion table in FIG. 9 is combined with the look-ahead code conversion tables having been described above with reference to FIGS. 7 and 8, the necessary looked-ahead amount of an information sequence is 5 blocks. So, when the information sequence is converted into a finite-state code conversion table via re-assignment of a code word delayed 5 blocks to an information word, it will have 1691 states. This number of states is very large.
Further, in case information is encoded according to a look-ahead code conversion table using the PP code word assignment technique having been proposed so face, the decoded code word constraint length will be larger than a decoded code word length resulted from a coding done according to the code conversion tables in FIGS. 2 and 3 and code conversion table in FIG. 6, for example. It should be noted here that the “decoded code word constraint length” is a number of blocks in a necessary code word that has to be held for sliding-block decoding.
As the decoded code word constraint length is larger, the decoder 16 is not only constructed to be more complex but the decoded error propagation length is larger and bit error rate after the decoding is worse. It should be noted here that the “decoded error propagation length” is a maximum number of bits whose one-bit error will possibly be propagated from a code sequence to an information sequence. Even in case the maximum number of minimum runs in sequence is limited finitely, the above problem will similarly occur.
FIG. 10 shows results of calculation of the number of code states at the time of coding, code word constraint length at the time of decoding and decoded error propagation length at the time of decoding in case the (1, 7) RLL code having been described with reference to FIGS. 2 to 9 is used. It should be noted however that in FIG. 10, the numbers of states in a combination of the code conversion tables in FIGS. 7 and 8 and a combination of the code conversion tables in FIGS. 7, 8 and 9, respectively, are those resulted from conversion of these look-ahead code conversion tables into a finite-state code conversion table with the aforementioned technique.
As will be seen in FIG. 10, the (1, 7) RLL code encoded under the coding rule in the combination of the code conversion tables in FIGS. 7 and 8 or that of the code conversion tables in FIGS. 7, 8 and 9, has 104 or 1691 code states at the time of coding, which is more than 20 times larger than the five states having been described with reference to the code conversion tables in FIGS. 2 and 3 or the code conversion table in FIG. 4 and than the four states having been described with reference to the code conversion table in FIG. 6. Also, as will be seen, the (1, 7) RLL code encoded under the coding rule in the combination of the code conversion tables in FIGS. 7 and 8 or that of the code conversion tables in FIGS. 7, 8 and 9, each using the PP code word assignment, has a decoded code word constraint length and decoded error propagation length about 2 times larger than those the (1, 7) RLL code encoded according to the code conversion tables in FIGS. 2 and 3, that in FIG. 4 or that in FIG. 6, and all the (1, 7) RLL codes thus encoded are considerably deteriorated.
That is, a code represented according to the look-ahead code conversion table using the already proposed PP code word assignment is more largely deteriorated in number of code states at the time of coding, code word constraint length at the time of decoding and error rate propagation length at the time of decoding than a code in which no PP code word assignment is effected. It has been demanded to improve these values.
Also, if the maximum number of minimum runs in sequence can be reduced, it is possible to effectively improve the bit error rate even if a defocusing, tangential tilt or the like occurs in an optical disk (recorder) player. However, the maximum number of minimum runs in sequence of the (1, 7) RLL code, that could be attained, is six. There has not been disclosed any technique for making the maximum number of minimum runs in sequence of the (1, 7) RLL code smaller than six.